package BinarySearchTree;

public class BinarySearchTree {
    public TreeNode rootNode;

    public void insert(int key) {
        if (rootNode == null) {
            rootNode = new TreeNode(key);
            return;
        }

        TreeNode curNode = rootNode;
        TreeNode parentNode = null;

        while (curNode != null) {
            if (curNode.val < key) {
                parentNode = curNode;
                curNode = curNode.rightNode;
            } else if (curNode.val > key) {
                parentNode = curNode;
                curNode = curNode.leftNode;
            } else {//二叉搜索树不存在两个相同的数
                return;
            }
        }

        curNode = new TreeNode(key);
        if (parentNode.val < key) {
            parentNode.rightNode = curNode;
        } else {
            parentNode.leftNode = curNode;
        }
    }

    public TreeNode search(int key) {
        if (rootNode == null) {
            return null;
        }

        TreeNode curNode = rootNode;

        while (curNode != null) {
            if (curNode.val < key) {
                curNode = curNode.rightNode;
            } else if (curNode.val > key) {
                curNode = curNode.leftNode;
            } else {
                return curNode;
            }
        }

        return null;
    }

    public void remove(int key) {
        if (rootNode == null) {
            return;
        }

        TreeNode curNode = rootNode;
        TreeNode parentNode = null;

        while (curNode != null) {
            if (curNode.val < key) {
                parentNode = curNode;
                curNode = curNode.rightNode;
            } else if (curNode.val > key) {
                parentNode = curNode;
                curNode = curNode.leftNode;
            } else {
                remove(key, parentNode, curNode);
                return;
            }
        }
    }

    private void remove(int key, TreeNode parentNode, TreeNode curNode) {
        if (curNode.leftNode == null) {
            if (curNode == rootNode) {
                curNode = curNode.rightNode;
            } else if (parentNode.leftNode == curNode) {
                parentNode.leftNode = curNode.rightNode;
            } else if (parentNode.rightNode == curNode) {
                parentNode.rightNode = curNode.rightNode;
            }
        } else if (curNode.rightNode == null) {
            if (curNode == rootNode) {
                curNode = curNode.leftNode;
            } else if (parentNode.leftNode == curNode) {
                parentNode.leftNode = curNode.leftNode;
            } else if (parentNode.rightNode == curNode) {
                parentNode.rightNode = curNode.leftNode;
            }
        } else {
            //找左树最大值
            TreeNode node = curNode.leftNode;
            TreeNode prevNode = curNode;

            while (node.rightNode != null) {
                prevNode = node;
                node = node.rightNode;
            }

            curNode.val = node.val;

            if (prevNode.leftNode == node) {
                prevNode.leftNode = node.leftNode;
            } else {
                prevNode.rightNode = node.leftNode;
            }

            /*//找右树最小值
            TreeNode node = curNode.rightNode;
            TreeNode prevNode = curNode;

            while (node.leftNode != null) {
                prevNode = node;
                node = node.leftNode;
            }

            curNode.val = node.val;

            if (prevNode.leftNode == node) {
                prevNode.leftNode = node.rightNode;
            } else {
                prevNode.rightNode = node.rightNode;
            }*/
        }
    }

    //将二叉搜索树转化为双向链表
    public TreeNode headNode;
    public TreeNode prevNode;
    public TreeNode convert(TreeNode rootNode) {
        if (rootNode == null) {
            return null;
        }

        convert(rootNode.leftNode);

        if (prevNode == null) {
            headNode = rootNode;
            prevNode = rootNode;
        } else {
            prevNode.rightNode = rootNode;
            rootNode.leftNode = prevNode;
            prevNode = rootNode;
        }

        convert(rootNode.rightNode);

        return headNode;
    }
}
